package leetcode.median;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class $93_RestoreIpAddresses {

    List<String> res = new ArrayList<>();

    Deque<String> path = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        int len = s.length();
        if (len < 4 || len > 12) {
            return res;
        }
        dfs(s, 0, 4, len);
        return res;
    }

    public void dfs(String s, int curIndex, int resDot, int len) {
        if (curIndex == len && resDot == 0) {
            res.add(String.join(".", path));
            return;
        }
        for (int i = curIndex;i < curIndex + 3;i++) {
            if (i >= len) {
                break;
            }
            if (len - i > resDot * 3) {
                // 如果剩余的元素数量 比剩余的.的数量的三倍还多
                continue;
            }
            if (judgeIpSegment(s, curIndex, i)) {
                String currentIp = s.substring(curIndex, i + 1);
                path.offerLast(currentIp);
                dfs(s, i + 1, resDot - 1, len);
                path.pollLast();
            }
        }
    }
    private boolean judgeIpSegment(String s, int left, int right){
        //定义一个表示整个字符的长度
        int len = right - left +1;
        //如果截取的大于等于2的字符的开头为0，就直接false
        if(len > 1 && s.charAt(left) == '0'){
            return false;
        }
        int res = 0;
        //拼接字符
        while(left <= right){
            res = res * 10 + s.charAt(left) - '0';
            left++;
        }
        return res >= 0 && res <= 255;
    }
}
